/**
 * @Question.Title: 最长回文子串
 * @Question.No: 5
 * @Author: Dang Qi
 * @Date: 2021-04-27 14:07:25
 * @Description: 
 */
//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 示例 3： 
//
// 
//输入：s = "a"
//输出："a"
// 
//
// 示例 4： 
//
// 
//输入：s = "ac"
//输出："a"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母（大写和/或小写）组成 
// 
// Related Topics 字符串 动态规划 
// 👍 3580 👎 0

package dq.leetcode.editor.cn;

public class LongestPalindromicSubstring {
    public static void main(String[] args) {
        Solution solution = new LongestPalindromicSubstring().new Solution();
        String s = "babad";
        System.out.println(solution.longestPalindrome(s));
    }
        //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int maxLen = 0;
        int start = 0;
        for(int len = 1; len <= n; len++){
            for(int i = 0; i <= n-len ; i++){
                int j = i + len - 1;
                //长度为1
                if(i == j){
                    dp[i][i] = true;
                }
                //长度为2
                else if(i +1 == j){
                    dp[i][j] = s.charAt(j) == s.charAt(i);
                }
                //长度大于2
                else if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1];
                }
                //更新最大值
                if(dp[i][j] && maxLen < len){
                    maxLen = len;
                    start = i;
                }
            }
        }
        return s.substring(start, start + maxLen);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}